"""
1191. K 次串联后最大子数组之和
中等
相关标签
相关企业
提示
给定一个整数数组 arr 和一个整数 k ，通过重复 k 次来修改数组。

例如，如果 arr = [1, 2] ， k = 3 ，那么修改后的数组将是 [1, 2, 1, 2, 1, 2] 。

返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 0，在这种情况下它的总和也是 0。

由于 结果可能会很大，需要返回的 109 + 7 的 模 。



示例 1：

输入：arr = [1,2], k = 3
输出：9
示例 2：

输入：arr = [1,-2,1], k = 5
输出：2
示例 3：

输入：arr = [-1,-2], k = 7
输出：0


提示：

1 <= arr.length <= 105
1 <= k <= 105
-104 <= arr[i] <= 104
"""


class Solution(object):
    def kConcatenationMaxSum(self, arr, k):
        """
        :type arr: List[int]
        :type k: int
        :rtype: int
        """
        mod = 10 ** 9 + 7
        #计算和，如果是负数，直接计算1和2的即可，因为后续加上也是减少的，可以忽略
        #如果是正数，则要把所有k带上，由于中间的只能取全部，所以实际上是 (k - 2) * sum + 两边界最大值
        #可以简单这么理解，把最右两边界看成一个整体，把除左右边界的中间看成一个整体，中间的只需要计算sum，挡sum>0则全部取，否则(k - 2) * max(sum,0)
        #再把边界看成一个整体，通过dp找到最大值，需要区分下大于1(都视为2，两个边界)和等于1的情况即可
        sum1 = sum(arr)
        #arr复制一份变成两分长
        if k >= 2:
            arr = arr * 2
            k -=2
        else:
            k-=1
        #
        dp = [0] * len(arr)
        dp[0] = max(arr[0],0)
        for i in range(1, len(arr)):
            dp[i] = max(dp[i - 1] + arr[i],0)
        if sum1 > 0:
            return (max(dp) +  (k *  sum1)%mod)%mod
        else:
            return max(dp)%mod

if __name__ == '__main__':
    print(Solution().kConcatenationMaxSum([2,-5,1,0,-2,-2,2], 2))
    print(Solution().kConcatenationMaxSum([-5,-2,0,0,3,9,-2,-5,4], 5))


